package com.hanxiaozhang.no10leetcode.link;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给定一个单向链表l0->ln，反转链表为L0→Ln→L1→Ln-1→L2→Ln-2→…，
 * 不能够改变链表中的值，只能改变节点本身的顺序。
 * 实例1:
 * Given 1->2->3->4, reorder it to 1->4->2->3.
 * 实例2:
 * Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
 *
 * @author hanxinghua
 * @create 2024/2/2
 * @since 1.0.0
 */
public class No143ReorderList {

    public static void main(String[] args) {

        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);

        Node head2 = new Node(1);
        head2.next = new Node(2);
        head2.next.next = new Node(3);
        head2.next.next.next = new Node(4);
        head2.next.next.next.next = new Node(5);


        method1(head1);
        LinkUtil.printLink(head1);

    }


    public static void method1(Node<Integer> head) {

        if (head == null) {
            return;
        }

        Node slow = head.next;
        Node fast = head.next.next;

        // 使用快慢指针找出中点位置，奇数个时，中间。偶数个时，中上
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 前半段(0 ~ slow)
        Node beforeNode = head;
        // 后半段(slow.next ~ 结尾)
        Node afterNode = slow.next;
        // 截断
        slow.next = null;

        // 后半段的node翻转
        Node secondRNode = reverse(afterNode);

        // 后半段的node插入到前半段的node中
        while (beforeNode != null && secondRNode != null) {
            Node tmp1 = beforeNode.next;
            Node tmp2 = secondRNode.next;
            // beforeNode的后继 指向 secondRNode
            beforeNode.next = secondRNode;
            // secondRNode的后继 指向 tmp1
            secondRNode.next = tmp1;
            // secondRNode 移动到 tmp2
            secondRNode = tmp2;
            // beforeNode 移动到 beforeNode后继的后继 即跳过插入的secondRNode
            beforeNode = beforeNode.next.next;
        }
    }



    private static Node reverse(Node node) {
        Node pre = null, cur = node, next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

}
